It is often necessary to compute the square of an n-bit (e.g., a 12-bit) value.
One conventional squaring method uses regular school book multiplication in which a 12-bit value is both the multiplier and the multiplicand as in the following example.
Hereinafter, the k""th bit from the right in the multiplicand and the m""th bit from the right in the multiplier are respectively referred to as xe2x80x9cmultiplicand bit kxe2x80x9d and xe2x80x9cmultiplier bit mxe2x80x9d. For example, the italicized bit in the above multiplication is referred to as xe2x80x9cmultiplicand bit 2xe2x80x9d. Furthermore, the k""th bit from the right in the m""th partial product is referred to as xe2x80x9cpartial product bit mkxe2x80x9d (or xe2x80x9cbit mkxe2x80x9d). For example, the underlined bit in the a""th (a16, b16, C16, d16, e16 and f16 as used herein, are a hexadecimal numerals respectively equal to 1010, 1110, 1210, 1310, 1410, and 1510, partial product is referred to as xe2x80x9cpartial product bit a9xe2x80x9d (or xe2x80x9cbit a9xe2x80x9d).
A partial product bit generator mk such as an AND gate mk is used to generate each partial product bit mk. One input terminal of each AND gate mk receives multiplicand bit k while the other input terminal receives multiplier bit m.
A circuit that implements this method requires a minimum of n2 (e.g., 144) AND gates to square an n-bit value. Additionally, in a Wallace tree of 3:2 carry save adders, each column may require up to nxe2x88x922 (e.g., 10) carry save adders. If each column has the same number of carry save adders, a total of 2n (e.g., 24) columns may require up to (2n) (nxe2x88x922)=2n2xe2x88x924n (e.g., 240) carry save adders. These AND gates and carry save adders occupy significant space on a die.
It is desirable to reduce the number of partial product bit generators and carry save adders required to square. By so doing, the partial product bit generator array and accompanying Wallace tree are made smaller and faster than in the conventional squaring circuit.
A circuit for squaring an n-bit value in accordance with the present invention is provided. The circuit includes a partial product bit generator which logically AND""s a bit of the n-bit value of weight 2k (k is an integer) with the same bit of weight 2k to provide a partial product bit of weight 22k on an output terminal. Another partial product bit generator has at least two input terminals configured to receive a bit of the n-bit value of weight 2k and a bit of weight 2m (m is an integers). The second partial product bit generator logically AND""s these bits and generates a partial product bit of weight 2(k+m+1). In one embodiment, the second partial product bit generator is the only partial product bit generator in the squaring circuit to logically AND the bit of weight 2m and the bit of weight 2k.
A method in accordance with the present invention is also provided by generating a first partial product bit of weight 22k from a bit of weight 2k in a first partial product bit generator. A bit of weight 2k is logically AND""ed with a bit of weight 2m to generate a second partial product bit of weight 2(k+m+1) in a second partial product bit generator. Another method includes providing the first and second partial product bit generators described above.
The circuit may also include other partial product bit generators. However, the required number of partial product bit generators is significantly reduced by about xc2xd compared to the conventional squaring circuits. For example, is squaring a 12-bit value, the number of partial product bit generators needed is reduced from 144 to 78, and even to 66 in one embodiment. The associated Wallace tree structure is simplified and made smaller because of this reduction in partial product bits. Therefore, a faster and smaller circuit for squaring is provided.
The present invention and its advantages and features will be more fully understood in light of the following detailed description and the claims.